#include "sort.h"
#include <iostream>
using namespace std;

void sort::print(int a[], int n)
{
    for (int i = 0; i < n; ++i) {
        cout << a[i] <<" " ;
    }
    cout << endl;
}

void sort::adjust_down(int a[], int beg, int lim)
{
    int max, left, right;
    while(true) {
        left = 2*beg+1;
        right = 2*beg+2;
        if(left<=lim && right<=lim) {
           max = (a[left]>a[right]?left:right);
        } else if(left<=lim) {
            max = left;
        } else return;
        if (a[beg]<a[max]) {
            swap(a[beg], a[max]);
            beg = max;
        } else return;
    }
}

void sort::mkheap(int a[], int n)
{
    int i = n-1;
    int parent;
    int max;
       
    while(i>0) {
        parent = ((i-1)>>1);
        if (i == parent*2 + 2) {
            max = (a[i]>a[i-1]?i:i-1);
            i -= 2;
        } else {
            max = i;
            i--;
        }
        if(a[max] > a[parent]) {
            swap(a[max], a[parent]);
            adjust_down(a, max, n-1);
        }
    }
}

void sort::heap_sort(int a[], int n)
{
    mkheap(a,n);
    while(n>1) {
        swap(a[0],a[n-1]);
        n--;
        adjust_down(a,0,n-1);
    }
}

void sort::bubble_sort(int a[], int n)
{
    int flag = 1;
    for (int i = 0; i < n-1; ++i) {
        for (int j = 1; j < n-i; ++j) {
            if(a[j-1]>a[j]) {
                swap(a[j-1], a[j]);
                flag = 0;
            }
        }
        if(flag) break;
    }
}

void sort::select_sort(int a[], int n)
{
    for (int i = 0; i < n; ++i) {
        int k = i;
        for (int j = i+1; j < n; ++j) if(a[j]<a[k]) k = j;
        if(k!=i){
            swap(a[k],a[i]);
        }
    }
}

void sort::insert_sort(int a[], int n)
{
    for (int i = 1; i < n; ++i) {
        int k = a[i];
        int j = i-1;
        for (; j>-1 && k<a[j]; --j) {
            a[j+1] = a[j];
        }
        a[j+1] = k;
    }
}

int sort::partition(int a[], int n)
{
    if (n==1) return 0;
    int i = 0, j = n;

    while(i<j) {
        while(a[0]>a[++i]) if(i==n-1) break;
        while(a[0]<a[--j]) if(j==0) break;
        if(i<j && a[j]<a[i]) swap(a[i],a[j]);
    }
    swap(a[0],a[j]);
    return j;
}

void sort::quick_sort(int a[], int n)
{
    if(n==0 || n == 1) return;
    int k = partition(a, n);
    quick_sort(a,k);
    quick_sort(a+k+1,n-k-1);
}

int sort::bsearch(int a[], int n, int key)
{
    int low = 0, high = n-1;
    int mid;
    while(low<high){
        mid = high+(high-low)>>1;
        if(key>a[mid]) low = mid+1;
        else if(key<a[mid]) high = mid-1;
        else return mid;
    }
    return -1;
}

void sort::combine_sort(int *a, int n)
{

}
